package lc;
import java.util.*;
import org.junit.*;

import util.BracketUtils;
public class Ex329 {
    class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            int times = 0, m = matrix.length, n = matrix[0].length;
            Queue<int[]> queue = new LinkedList<>();
            //查找头元素
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i > 0 && matrix[i][j] > matrix[i - 1][j]) {
                        continue;
                    }
                    if (j > 0 && matrix[i][j] > matrix[i][j - 1]) {
                        continue;
                    }
                    if (i < m - 1 && matrix[i][j] > matrix[i + 1][j]) {
                        continue;
                    }
                    if (j < n - 1 && matrix[i][j] > matrix[i][j + 1]) {
                        continue;
                    }
                    queue.offer(new int[]{i, j});
                }
            }

            while (!queue.isEmpty()) {
                int size = queue.size();
                Set<String> set = new HashSet<>();
                for (int k = 0; k < size; k++) {
                    int[] cur = queue.poll();
                    int i = cur[0], j = cur[1];
                    if (i > 0 && matrix[i][j] < matrix[i - 1][j]) {
                        if (!set.contains((i - 1) + "_" + j)) {
                            queue.offer(new int[]{i - 1, j});
                            set.add((i - 1) + "_" + j);
                        }  
                    }
                    if (j > 0 && matrix[i][j] < matrix[i][j - 1]) {
                        if (!set.contains((i) + "_" + (j - 1))) {
                            queue.offer(new int[]{i, j - 1});
                            set.add((i) + "_" + (j - 1));
                        }  
                    }
                    if (i < m - 1 && matrix[i][j] < matrix[i + 1][j]) {
                        if (!set.contains((i + 1) + "_" + j)) {
                            queue.offer(new int[]{i + 1, j});
                            set.add((i + 1) + "_" + j);
                        }  
                    }
                    if (j < n - 1 && matrix[i][j] < matrix[i][j + 1]) {
                        if (!set.contains((i) + "_" + (j + 1))) {
                            queue.offer(new int[]{i, j + 1});
                            set.add((i) + "_" + (j + 1));
                        }  
                    }   
                    
                }
                times++;
            }
            return times;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[9,9,4],[6,6,8],[2,1,1]]");
        System.out.println(s.longestIncreasingPath(nums));
    }
}
